"""
假设链表节点的结构如下
"""

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


"""
1.以下函数对给定的链表有什么作用？
    倒序输出一维链表中各节点数据
"""
def fun1(head):
    """
    倒序输出一维链表中各节点数据
    """
    if(head == None):
        return  # 空链表返回空值
    fun1(head.next) # 非空链表往后索引
    print(head.data, end = " ") # 输出节点内数据


""" 
2 以下函数对给定的链表有什么作用？

    按照特定的顺序打印链表中的元素。
    先打印当前节点的数据，然后递归地对当前节点的下一个节点的下一个节点执行相同的操作，最后再打印当前节点的数据。
    使得每个节点的数据都会被打印两次，且第一次打印在第二次打印之前。
    
    若有链表  1 3 5 7 9
    则输出：  1 5 9 9 5 1
    
    若有链表 2 4 6 8 
    则输出： 2 6 6 4
    
    类似出入栈
 """
def fun2(head):
    """
    按照特定的顺序打印链表中的元素。
    先打印当前节点的数据，然后递归地对当前节点的下一个节点的下一个节点执行相同的操作，最后再打印当前节点的数据。
    使得每个节点的数据都会被打印两次，且第一次打印在第二次打印之前。
    """
    if(head == None):
        return  #空链表返回空值
    print(head.data, end = " ") # 非空链表打印当前节点数据
    if(head.next != None ): # 保证索引到头结点下下节点情况下
        fun2(head.next.next)    # 对头结点的下下节点执行fun2递归
    print(head.data, end = " ") # 若节点 后续无节点 / 为倒数第二节点 输出当前节点数据


    """
     3 给定一个单链表，任务是找到链表的中间。如果节点数为偶数，则将有两个中间节点，因此返回两个中间节点。
    例子
        Input: linked list: 1->2->3->4->5
        Output: 3

        Input: linked list = 10-> 20-> 30-> 40-> 50-> 60
        Output: 30, 40
    """
def find_mid_node(head:Node):
    slow = fast = head
    prev = None
    while fast and fast.next:
        # fast非空 且 下一节点非空
        fast = fast.next.next   # fast节点每次前进两节点
        prev = slow  # prev 切换到当前slow节点
        slow = slow.next    # slow节点每次前进一节点
    if fast:    # fast下节点为空时，也即fast位置指向单数索引值
        return slow.data
    else:   # fast节点正好指空，也即fast位置指向双数索引值时指空，共双数节点
        return ( prev.data, slow.data )


"""
     4 给定一个链表，任务是通过更改节点之间的链接来反转链表。
    例子:
     Input: Linked List = 1-> 2-> 3-> 4-> NULL
        Output: Reversed Linked List = 4-> 3-> 2-> 1-> NULL
     Input: Linked List = 1-> 2-> 3-> 4-> 5-> NULL
        Output: Reversed Linked List = 5-> 4-> 3-> 2-> 1-> NULL
     Input: Linked List = NULL
        Output: Reversed Linked List = NULL
     Input: Linked List = 1->NULL
        Output: Reversed Linked List = 1->NULL
"""
def reversed_LinkList(head: Node):
    # 类似头插法实现
    prev = Node(None)  # 初始化记录位置为None
    current = head  # 对当前节点做复制到current
    while current is not None:  # 当前节点非空
        next_node = current.next  # 记录下一节点为next_node
        current.next = prev  # 将复制所得节点指向prev
        prev = current  # prev作为头结点 重定向到复制和修改后的current
        current = next_node  # 将current节点重赋值为下一节点next_node
    delNone = prev
    while delNone.next.next is not None:
        delNone = delNone.next
    delNone.next = None  # 清除多出的None节点
    return prev  # 返回新的头结点


"""
     5 给定一个包含 M 个节点的链表和一个数字 N，找到从链表末尾开始的第 N 个节点的值。
        如果末尾没有第 N 个节点，则打印-1。
     Input: 1-> 2-> 3-> 4, N = 3
        Output: 2
     Input: 35-> 15-> 4-> 20, N = 4
        Output: 35
"""
def find_index_reverse(head:Node, N:int):
    pos = rev = reversed_LinkList(head)
    # 反转链表后变成寻找第N节点值 记录新的头结点为pos 记录另一头结点为rev
    num = 0  # 计数器初始为0
    while pos is not None and num != N-1:
        # 指示节点非空 且 计数器未达指定N位
        pos = pos.next
        num += 1
    if pos is None:  # 指示节点遍历链表后仍未达N位
        return -1
    reversed_LinkList(rev) # 从rev重新反转
    return pos.data  # 计数器达位 输出目标data

"""
 6 给定两个单向链表，任务是将第二个列表的节点插入到第一个列表的第一个列表的替代位置，
    如果第二个列表的节点更长，则留下第二个列表的剩余节点。
Input:  head1: 1->2->3
        head2: 4->5->6->7->8
    Output: head1: 1->4->2->5->3->6
            head2: 7->8
 Input:  head1: 10->12->21
         head2: 3->1->4
    Output: head1: 10->3->12->1->21->4
            head2: <empty>        
 """
def merge_ll(head1:Node, head2:Node):
    """
    将第二个列表的节点插入到第一个列表的第一个列表的替代位置，
    如果第二个列表的节点更长，则留下第二个列表的剩余节点。
    另外建议 import copy 然后用copy.deepcopy()方法做对象的复制
    """
    dummy = Node(None)  # 新链表初始节点
    current = dummy
    while head1 and head2:
        # 遍历两个链表，交替插入节点
        current.next = head1
        head1 = head1.next
        current = current.next
        current.next = head2
        head2 = head2.next
        current = current.next
    # 如果其中一个链表还有剩余节点，直接连接到结果链表的末尾
    if head1:
        current.next = head1
    if head2:
        current.next = head2
    return dummy.next


"""
7   给定一个单向链表。任务是从给定列表（如果存在）中删除重复项（具有重复值的节点）
        注意：尽量不要使用额外的空间。节点以排序方式排列。
    Input:LinkedList: 2->2->4->5
        Output: 2-> 4-> 5
    Input:LinkedList: 2->2->2->2->2
        Output: 2
"""
def del_cp_val(head:Node):
    """
    给定一个单向链表。任务是从给定列表（如果存在）中删除重复项（具有重复值的节点）
    注意：尽量不要使用额外的空间。节点以排序方式排列。
    """
    valList = list()
    pos = head
    rev = pos
    while pos.next is not None:
        if pos.next.data in valList:
            pos.next = pos.next.next
        valList.append(pos.data)
        rev = pos
        pos = pos.next
    if pos.data in valList:
        rev.next = None


"""
8   给定一个单向链表，任务是将其转换为循环链表。
"""
def circular_linklist(head:Node):
    """
    对给定单项链表转换为循环链表
    返回头指针head和尾指针rear
    """
    # 空表/单节点：返回自己节点
    if not head or not head.next:
        return head, head
    # 找到链表的尾节点
    tail = head
    while tail.next:
        tail = tail.next
    # 将尾节点的next指针指向头节点，形成循环链表
    tail.next = head
    return head, tail

"""
9   给定一个 n*n 大小的 Matrixmat，任务是构造给定矩阵的 2D 链表表示。
"""
def construct_2D_linked_list(mat):
    if not mat or not mat[0]:
        return None
    Size = len(mat)
    head = Node(None)
    current = head
    for i in range(Size):
        for j in range(Size):
            current.next = Node(mat[i][j])
            current = current.next
    return head.next


"""
    链表初始化
"""
# 定义链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(2)
node5 = Node(5)
node6 = Node(3)
node7 = Node(5)
head = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
node6.next = node7
# 定义另一链表
nodeano1 = Node(30)
nodeano2 = Node(20)
nodeano3 = Node(10)
nodeano4 = Node(0)
headano = nodeano1
nodeano1.next = nodeano2
nodeano2.next = nodeano3
nodeano3.next = nodeano4
# Linklist打印
def Linklistprint(head):
    pos = head
    while pos.next is not None:
        print(pos.data, end=" -> ")
        pos = pos.next
    print(pos.data)


"""
    链表方法测试
"""
# 打印初始链表
print("Linklist head:")
Linklistprint(head)
print("Linklist headano:")
Linklistprint(headano)
# 打印fun1结果
print("\n\nfun1 result:")
fun1(head)
print("\nNow Linklist:")
Linklistprint(head)
# 打印fun2结果
print("\n\nfun2 result:")
fun2(head)
print("\nNow Linklist:")
Linklistprint(head)
# 打印find_mid_node结果
print("\n\nfunction Find_Mid_Node result:")
print(find_mid_node(head))
print("Now Linklist:")
Linklistprint(head)
# 打印reversed_LinkList结果
print("\n\nfunction Reversed_LinkList result:")
rev = reversed_LinkList(head)
Linklistprint(rev)
head = reversed_LinkList(rev)
print("\nNow Linklist:")
Linklistprint(head)
# 打印find_index_reverse结果
print("\n\nfunction Find_Index_Reverse result:")
print(find_index_reverse(head,3))
print("Now Linklist:")
Linklistprint(head)
"""
print()
k1 = head
k2 = headano
print("merge_ll")
Linklistprint(merge_ll(k1,k2))
print("Now Linklist:")
Linklistprint(head)
print("Now Another Linklist:")
Linklistprint(headano)
"""
# 打印 结果
print("\n\nfunction  result:")
del_cp_val(head)
print("Now Linklist:")
Linklistprint(head)